COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2BASB30\M3NGR25\M4NGR20\M5NGB30\M6BASI30\F2\CSTANFORD UNIVERSITY
C00028 ENDMK
C⊗;
\\M1BASL30;\M2BASB30;\M3NGR25;\M4NGR20;\M5NGB30;\M6BASI30;\F2\CSTANFORD UNIVERSITY
\F3\CSTANFORD, CALIFORNIA 94305
\F4COMPUTER SCIENCE DEPARTMENT\←L\-R\/'7;\+R\→.\→S   Telephone:
\←S\→.415-497-4971
\F1\CAug 29, 1975









Robert L. Ashenhurst, ACM Editor-in-Chief
Institute for Computer Research
The University of Chicago
Chicago, Ill.  60637


Dear Dr. Ashenhurst:

\JPerhaps this letter should be addressed to the SIGCSE instead of to the
membership at large, but I feel that education is the business of the
whole community. 
The letter addresses itself particularly to the undergraduate educational
policies.
The general thesis of these remarks is that a fundamental
restructuring of \F6Curriculum 68\F1
is long overdue. 
In particular the beginning courses,
which will make or break a department, must reflect a more unified look at the
field of Computer Science giving the new student motivation and perspective.
Unless a beginning student can be convinced that Computer Science
is something other than programming or hardware, then he becomes easy prey
for other departments. As presently constituted, Curriculum 68 does little
to dispel  such doubts. It is my belief that much of the fault lies in the
data structures course, I1. 
Too many departments have copied
the I1-Data Structures description without proper regard for the importance
of its place in the 68-graph. 

In many universities, I1 is the first \F6real\F1 computer science course.
The previous courses are more applications courses, covering basic programming
and perhaps hardware and finite mathematics. The difficulty is that such a background
does not adequately prepare a student for the usual dose of I1.  
All too frequently  this course
deals too much with tricks and techniques and too little with ideas and
motivation. 
Other than a possible interest in toy problems
or a desire to please the instructor, why should a student with such a meager
background be  interested in data structures?

Once you start  questioning the
content of I1, other doubts arise. Why use machine language to describe 
data structures? We don't require machine language for courses on numerical analysis 
so why not treat data structures with the same respect?
It is therefore desirable to use a high level language to
describe data structure algorithms. 

We should also think about the courses which will follow I1
and what we can do to prepare the student for them. We should, if possible,
prepare students for courses on translator construction,
systems programming, and for less traditional 
courses on correctness, structured programming, programming methodology.
I believe we motivate these later courses by giving additional care to the
preparation of I1.


First we address the problems of motivating the current content of I1.
What was the \F6original\F1 motivation for these techniques of data structuring? 
The  tricks and techniques arose from real needs of programmers working
on increasingly sophisticated projects. Though they arose from diverse
problem areas, many  arose in the context of language implementation; and
the \F6ideas\F1 to be presented in I1 can all be handled in a discussion
such an implementation.
Now interjecting language implementation into our discussion seems like
a step backwards. Before anyone should undertake such a project he must
have a clear understanding of all of the details of the language. 

What language should we pick? Many exist and any, from
machine language to high level language, could be used.
For a course in the position of I1 we also want a language which we can use to
talk about data structures at some level of abstraction.
We are first interested in motivating the ideas, not in bit-pushing and efficiency.
So we would like a high level language suitable for describing data structures
and their manipulations; we will talk about the techniques  of I1 
when we discuss implementation of the language and
need to understand the issues of representation of data structures and the
mechanization of data-structure algorithms.

What requirements should such a language have?  It's syntax should be simple
so that the students can become reasonably proficient in a very short time.
It should have recursion for several reasons: many data structure problems
are most easily described with this construct; the implementation
mechanisms underlying recursion can be motivated easily when we come to
implementation questions.

Since we are teaching programming style,  we must have the ability to describe
abstract data structures and demonstrate to the student the benefits of 
representation-independent programming and stepwise-refinement;
but we must also convince the student that these
abstractions can indeed be turned into programs which run on a machine.

One on the most troublesome areas for students is in developing
an understanding binding strategies. Indeed one of the most difficult problems
of language design is the proper understanding of binding and environments. 
We should take care to
discuss the implications call-by-name, call-by-value, and procedure-valued 
variables. After a proper regard for their complexity is developed
the student will be prepared to handle the data structure problems which
arise in the implementations.

As we are describing the  language  with
an eye both towards evaluation and implementation, we should
be most careful in giving a precise description of the meaning of each
construct of the language. Here we should introduce the student to
the problems of semantics and language specification. Since this is
to be a course on data structures a natural specification of our
language might entail an operational or interpreter definition.
The project entails a description of evaluation mechanism as a program
in our language and a description of language constructs as data structures.
This has at least two benefits. First, it shows a non-trivial application
of data structures. Second, the operational description is a high-level
implementation of our language. It will give a concise specification of
even the most troublesome constructs.
The precision and level of detail will be
invaluable when we begin a discussion of the concrete implementation.


Once the operational description is  digested the natural question is 
implementation on a \F6real\F1 machine.
This discussion outlines the static orgainzation of a machine,
giving insights and motivation for problems of 
data structures, storage management, and symbol table orgainzation.

The discussion of the run-time management of such a programming language 
will also involve careful applications of data structuring.
A natural way to approach these questions of the dynamic structure of the
machine is to discuss compilers. 
Given a clear understanding of the evaluation 
mechanism and an understanding of the real machine  we can start asking
what structure we need to impose of the hardware to assure proper execution.
The mechanisms for recursion, and binding strategies arise here.
The problems binding strategies are easily discussed by this point in the 
development.

The questions of language specification lead  quite naturally to
more theoretical discussions of semantics of programming languages
and correctness and equivalence of programs.
The beginning student must be made aware of the importance of correctness 
considerations and a course dealing with abstract data structures, programming
style and language description and implementation is a natural setting for 
such a discussion.

The language we pick for I1 should also be  \F6real\F1. There is a certain soothing
effect on the student if he knows that he is not the subject in some
ill-conceived language design experiment.
Many languages still meet these requirements. LISP is  one
which has a rich history of interesting
programming examples. 
We can  cite fifteen years of
most interesting artificial intelligence programs or clever compilers, or
advanced interactive debuggers or editors, all written in LISP.

Once the ideas involved in data structure manipulation are seen in a
rich environment like that of language implementation, 
we can easily motivate questions about efficiency.
Questions of storage and control regimes lead naturally to more complex
representations of data structures. It is at this point that the student
is aware of the \F6reasons\F1 for studying data structures.
Along the way we have also introduced them to abstraction as a means of
controlling complexity, recursion as a programming technique, step-wise
refinement as a programming style, 
operational definitions of programming languages,
and the related problems of translator construction.
Not only does he understand the data structuring techniques, but he understands
some of the contexts in which they have been found useful.


Perhaps this seems like a lot for a beginning student. 
It has turned out not to be the case. 

So where are we? 
I have claimed the most of the content of I1 is very naturally motivated
by courses which come \F6after\F1 I1.  I have claimed that we need a course
to bridge the gap between computing courses and computer science courses.
Just what are we advocating? 
Our initial sortie into
data structures has turned into a course on language design and
just about everything else.  
What we claim then, is that the 68-graph isn't just out-of date, it's wrong.
The presentation we are advocating isn't new; all but a few of the ideas 
are present in 
John McCarthy's early work on LISP and abstract syntax; 
all these papers were available in 1968.
McCarthy is not even mentioned in the bibliography attached to I1!
What is normally taught as
a course on data structures, does not belong at 
a point like I1 in the ACM graph. 
The typical student's background just is
not sufficient to support this approach.  
Such a course would have value later in the student's career when
problems of efficiency have relevance.
But I1 should be a feeder course for 
courses on translator construction, systems programming, semantics of programming
languages, and the rest of the courses in the department. The computer science
major
must get a realistic overview of the  field and the interested bystander
must be tantalized into joining the ranks.

There have been several attempts at revising
Curriculum 68 but I have not seen a major restructuring proposed.
An early course which unifies the material which is unique to computer science,
particularly the software  areas, is needed badly.
Hardware courses require a reasonable background in \F6real\F1
engineering and physics. But what \F6real\F1 background do you need to
be a programmer? The usual answer is "none". And that's where the problems
start. Many departments  justify their existence by 
offering programming classes, supplying cannon fodder for other departments
and for industry.
Computing classes most certainly should be taught by computer scientists,
but the departments must go beyond this image of a service bureau. They must
become less sensitive to
the immediate needs of industry and stop confusing dispensation of 
technical skill with education.
The discipline is not in a sufficiently well-defined stage that we
can be dispensers of conventional wisdom; we should be advocating
how things \F6should be\F1 rather than pontificating about how things \F6are\F1.
Dijkstra's \F6Humble Programmer\F1 should be required reading.

Perhaps my approach smacks of elitism; I claim not so. I claim that many, if
not all, of the
current difficulties  hiding under the blanket of \F6The Software Problem\F1
are traceable to poorly trained programmers. I claim that we must expect
professional programmers to be as sophisticated as their engineering or mathematical
counterparts. 
Indeed, many people have noted that if the practitioners in other technical fields
performed in the cavalier manner of current programming methodology, the death
toll would be enormous.
The violence done by poor programming is not so visible but is at least as severe.
The problems in current programming practice are not those of efficiency
but are those of \F6correctness\F1.
People write buggy programs.
Faster machines will not solve these problems;
faster machines or automatic programming systems will not 
overcome poorly educated programmers. I reiterate: these remarks are directed
toward undergraduate education; graduate students should know how to
take care of themselves. Other technical departments expect their undergraduates 
to become conversant with the basic tools of the discipline. The basic tools
of computer science are not programming languages, \F6per se\F1, but are
the cultivation of methods of thought. It has been remarked that few programmers
discover recursion; they are told about it. That's a shame. 

There is a succinct statement by C. Strachey which reflects my attitude about
programming languages and therefore my approach to data structures:
	\F6"I always worked on programming languages because it seems to me that
until you could understand those, you couldn't understand computers. Understanding
them doesn't really mean only being able to use them. A lot of people can use them
without understanding them."\F1
\.
\←L\→S\←R\-L\/'2;\+L\→L

Yours sincerely,



John R. Allen 
Research Associate
Computer Science Dept
Artificial Intelligence Labs

\←S\→L
LISP is an excellent way to take intelligent but technically naive students rapidly
to advanced topics in such a way that a coherent picture of much of
modern computer science is presented.